/* 

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

 

示例 1：

输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：

输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。
示例 3：

输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：

输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
 

提示：

1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 '#'。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/backspace-string-compare
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/


/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */

// 堆栈
var backspaceCompare = function (S, T) {
    const build = function (str) {
        const stack = [];
        for (let i = 0, len = str.length; i < len; i++) {
            if (str[i] != "#") {
                stack.push(str[i]);
            } else if (stack.length) {
                stack.pop();
            }
        }

        return stack.join("");
    }

    return build(S) === build(T);
};

// 双指针
var backspaceCompare = function (S, T) {
    let i = S.length - 1,
        j = T.length - 1;
    let backspaceNumsOfS = 0,
        backspaceNumsOfT = 0;

    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (S[i] === "#") {
                backspaceNumsOfS++;
                i--;
            } else if (backspaceNumsOfS !== 0) {
                backspaceNumsOfS--;
                i--
            } else {
                break;
            }
        }

        while (j >= 0) {
            if (T[j] === "#") {
                backspaceNumsOfT++;
                j--;
            } else if (backspaceNumsOfT !== 0) {
                backspaceNumsOfT--;
                j--
            } else {
                break;
            }
        }

        if (S[i] !== T[j]) return false;
        i--;
        j--;
    }

    return true;
};